package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.LinkedProblem;
import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * https://leetcode.com/problems/longest-consecutive-sequence/
 * 最长连续序列
 * <p>
 * in O(n) complexity. 直接不能排序了
 * <p>
 * 并查集, Union Find // 艹, 这根本不叫并查集
 * <p>
 * AC了, 但是1061 ms, faster than 5.04%
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC128 implements TreeProblem, GraphProblem {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        HashMap<Integer, Boolean> unionFind = new HashMap<>();//boolean表示是否有next数
        for (int num : nums) {
            int pre = num - 1, next = num + 1;
            if (unionFind.containsKey(pre)) unionFind.put(pre, true);
            if (unionFind.containsKey(next)) {
                unionFind.put(num, true);
            } else {
                unionFind.put(num, false);
            }
        }//On时间 On空间
        int longest = 0;
        for (Integer key : new ArrayList<>(unionFind.keySet())) {
            int cur = key;
            while (unionFind.containsKey(cur) && unionFind.get(cur)) {
                cur = cur + 1;
            }
            longest = Math.max(longest, cur - key);
        }
        return longest + 1;
    }

    public static void main(String[] args) {
        System.out.println(new LC128().longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println(new LC128().longestConsecutive(new int[]{100, 4, 101, 1, 102, 3, 9}));
    }
}
